/*
==================================================================
* 版权所有 © 2025 CaryXiong
* Copyright (C) 2025 CaryXiong(a1816101108@outlook.com)
*
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
===================================================================
*/




#include<iostream>
using namespace std;

template<class DataType>
class Sort{
    public:
        Sort(DataType a[], int length);
        void BubbleSort_Dec();
        void BubbleSort_Asc();
        void SelectSort_Dec();
        void SelectSort_Asc();
        void InsertSort_Dec();
        void InsertSort_Asc();
        void ShellSort_Dec();
        void ShellSort_Asc();

        void PrintList();
    private:
        DataType *data;
        int length;
};

template<class DataType>
Sort<DataType> :: Sort(DataType data[], int length){
    this->length = length;

    this->data = new DataType[length];
    for(int i=0; i<length; i++){
        this->data[i] = data[i];
    }
}

template<class DataType>
void Sort<DataType> :: BubbleSort_Dec(){
    DataType exchange, bound, temp;
    exchange = length-1;

    while(exchange != 0){
        bound = exchange;
        exchange = 0;

        for(int i=0; i<bound; i++){
            if(data[i] < data[i+1]){
                temp = data[i];
                data[i] = data[i+1];
                data[i+1] = temp;
                exchange = i;
            }
        }
    }
}

template<class DataType>
void Sort<DataType> :: BubbleSort_Asc(){
    DataType exchange, bound, temp;
    exchange = length-1;

    while(exchange != 0){
        bound = exchange;
        exchange = 0;

        for(int i=0; i<bound; i++){
            if(data[i] > data[i+1]){
                temp = data[i];
                data[i] = data[i+1];
                data[i+1] = temp;
                exchange = i;
            }
        }
    }
}

template<class DataType>
void Sort<DataType> :: SelectSort_Dec(){
    int temp, index;

    for(int i=0; i<length-1; i++){
        index = i;
        for(int j=i+1; j<length; j++){
            if(data[j] > data[index]) index = j;
        }
        if(index != i){
            temp = data[i];
            data[i] = data[index];
            data[index] = temp;
        }
    }
}

template<class DataType>
void Sort<DataType> :: SelectSort_Asc(){
    int temp, index;

    for(int i=0; i<length-1; i++){
        index = i;
        for(int j=i+1; j<length; j++){
            if(data[j] < data[index]) index = j;
        }
        if(index != i){
            temp = data[i];
            data[i] = data[index];
            data[index] = temp;
        }
    }
}

template<class DataType>
void Sort<DataType> :: InsertSort_Dec(){
    int temp, j;
    for(int i=1; i<length; i++){
        temp = data[i];
        for(j=i-1; j>=0 && temp>data[j]; j--){
            data[j+1] = data[j];
        }
        data[j+1] = temp;
    }
}

template<class DataType>
void Sort<DataType> :: InsertSort_Asc(){
    int temp, j;
    for(int i=1; i<length; i++){
        temp = data[i];
        for(j=i-1; j>=0 && temp<data[j]; j--){
            data[j+1] = data[j];
        }
        data[j+1] = temp;
    }
}

template<class DataType>
void Sort<DataType> :: ShellSort_Dec(){
    int d, j, temp;
    for(d = length/2; d>0; d=d/2){
        for(int i=d; i<length; i++){
            temp = data[i];
            for(j=i-d; j>=0 && temp>data[j]; j=j-d){
                data[j+d] = data[j];
            }
            data[j+d] = temp;
        }
    }
}

template<class DataType>
void Sort<DataType> :: ShellSort_Asc(){
    int d, j, temp;
    for(d = length/2; d>0; d=d/2){
        for(int i=d; i<length; i++){
            temp = data[i];
            for(j=i-d; j>=0 && temp<data[j]; j=j-d){
                data[j+d] = data[j];
            }
            data[j+d] = temp;
        }
    }
}

template<class DataType>
void Sort<DataType> :: PrintList(){
    for(int i=0; i<length; i++) cout << data[i] <<"\t";
    cout << endl;
}

int main(){
    int a[10] = {1,2,3,4,5,6,7,8,9,10};
    Sort<int> S(a,10);
    cout << "原始数据表内容：";
    S.PrintList();
    cout << endl;

    cout << "冒泡排序降序：\t";
    S.BubbleSort_Dec();
    S.PrintList();
    cout << endl;
    cout << "冒泡排序升序：\t";
    S.BubbleSort_Asc();
    S.PrintList();
    cout << endl;
    cout << "选择排序降序：\t";
    S.SelectSort_Dec();
    S.PrintList();
    cout << endl;
    cout << "选择排序升序：\t";
    S.SelectSort_Asc();
    S.PrintList();
    cout << endl;
    cout << "插入排序降序：\t";
    S.InsertSort_Dec();
    S.PrintList();
    cout << endl;
    cout << "插入排序升序：\t";
    S.InsertSort_Asc();
    S.PrintList();
    cout << endl;
    cout << "希尔排序降序：\t";
    S.ShellSort_Dec();
    S.PrintList();
    cout << endl;
    cout << "希尔排序升序：\t";
    S.ShellSort_Asc();
    S.PrintList();
}